package com.year_23.april;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author: jsh
 * @create: 2023/4/27 21:37
 * @Description:    1048 最长字符串链
 *                  https://leetcode.cn/problems/longest-string-chain/
 * @FileName: Day27
 * @History:
 * @自定义内容：
 */
public class Day27 {

    public int longestStrChain(String[] words){
        int res = 1;
        Map<String,Integer> map = new HashMap<>();
        Arrays.sort(words,(a, b) -> a.length() - b.length());
        for (String s : words){
            map.put(s, 1);
            for (int i = 0; i < s.length(); i++) {
                String temp = s.substring(0,i) + s.substring(i+1, s.length());
                if (map.containsKey(temp)){
                    map.put(s, Math.max(map.get(s), map.get(temp) +1 ));

                }
            }
            res = Math.max(res, map.get(s));
        }

        return res;
    }
}
